.SS(Macros and special forms,macros,P57:)
.P18:
Recall our discussion of ⊗→special forms↔← in {yonss(P8}).
Special forms have been used for two purposes: to control the evaluation
of arguments (conditional expressions, quoted expressions,
%3and, or%*, etc.), and to create the effect of functions with an indefinite 
number of arguments (%3list, append, plus, ...%*)
Even though we wish to define
some functions as if they had an arbitrary number of arguments, when
we  call  the function, the number of arguments to be
applied %6is%* known. In particular, when the compiler is examining the
program, the number of arguments is known. The compiler can often
compile better code than calls on %3eval%*.

.BEGIN GROUP;
Assume, for example, we wish to define %3plus%* as a function with
an indefinite number of arguments such that:

.BEGIN CENTERIT;SELECT 3;GROUP;
←plus[4;5] = 9
←plus[4;5;6] = 15
←plus[4;add1[2];4] = 11
.END
.END

That is, %3plus%* is to  have the properties of a function: its arguments
are to be evaluated (from left to right); but it can take an arbitrary number
of arguments.
We can  define %3plus%* in terms of a %2binary%*
addition function, %3*plus%*.

.BEGIN CENTERIT;SELECT 3;GROUP;

←plus[4;5] = *plus[4;5] = 9
←plus[4;5;6] = *plus[4;*plus[5;6]] = 15
←plus[4;add1[2];4] = *plus[4;*plus[add1[2];4]] = 11
.END

That is, we %2expand%* calls on %3plus%* into a composition of calls on
%3*plus%*.
%3plus%* is being used as a %2macro%* and the expansion process in terms
of %3*plus%* is called %2macro expansion%*. Thus  macro expansion
generates a composition of calls on %3*plus%*.
Realize too, that since LISP programs must perform equivalently when
interpreted, we must recognize a macro construction inside %3eval%*.

The body of a macro is a 
λ-expression of %2one%* argument. The %2use%* of a macro looks just like
an ordinary function call, but what is bound to the λ-variable is the whole
call on the macro.
The task of the macro body is to
expand the macro call and return this expansion as its value.

.BEGIN TURN ON "#";
Let's define %3<%4m%*=%1 to mean "#is#defined#to#be#the#macro#...".
Then a simple macro definition of %3plus%* might be:
.END

.BEGIN SELECT 3;TABIT2(10,25);GROUP;

.P58:
\plus <%4m%*= λ[[l]\[eq[length[l];3] → concat[*PLUS;cdr[l]]
\\ %et%* → list[*PLUS;second[l];concat[PLUS;rest[rest[l]]]]]]
.END

Thus a call %3(PLUS 3 4 5)%* would bind %3l%* to %3(PLUS 3 4 5)%* and
the evaluation of the body would result in %3(*PLUS 3 (PLUS 4 5))%*.
Evaluation of this expression would result in another call on the macro.
This time %3l%* would be bound to %3(PLUS 4 5)%*. Now
%3eq[length[l];3]%* %2is%* true and the value returned is %3(*PLUS 4 5)%*.
This can be evaluated, giving 9, and finally the outermost call on %3*PLUS%*
has all its arguments evaluated, and we get the final answer, 12.

Since the body
of a macro has available all of the evaluation mechanism of LISP, and
since the program structure of LISP is also the data structure, we can
perform arbitrary computations inside the expansion of the macro.

Notice that %3SETQ%*  can easily be defined as a macro
over %3SET%*:
.BEGIN CENTERIT;SELECT 3;GROUP;

←setq <%4m%*= λ[[l] list[SET;list[QUOTE;second[l]];third[l]]].
.END
.P54:
where "<%4m%*=" has the effect of establishing a macro definition.


The idea of macro processing is not recent.  Some of the earliest assemblers
had extensive macro facilities.  Lately macros have been used as a means
of extending so-called high level languages.
One of the most simple kinds of macros is %2textual substitution%*.
That is, when a use of a macro is detected we simply replace the call by its
body.  A slightly more sophisticated application is the %2syntax macro%*.
Everytime we come across an application of a syntax macro the expander 
processes it as if it had never been seen before even though much
of the expansion is repetitious. That is, syntax macros have no memory.

%2computational macros%* are an attempt to reduce some of this repetition.
In this scheme a certain amount of processing is done at the time the macro
is %2defined%*. For example a computational subtree reflecting the body of the
macro might be formed.  Then whenever the macro is %2used%* we can
simply make a copy of this subtree and "glue" this subtree into the parse-tree
which we are building.  This computational subtree is commonly formed by passing
the body of the macro through the compiler in a 
"funny" way.  The main problem with the computational macro is that there are
many desirable macros which have no such subtree, or there is other information
 necessary to process the macro.  There are solutions to this problem,
one of which closely parallels the abstract syntax ideas of McCarthy.
All of these styles of macros are subsets of the LISP macros.


.CENT(Problems)

I.  Define %3list%* and %3append%* as macros. You may use only
the LISP primitives (functions, predicates, conditionals and
recursion) and a binary function, %3*append%*.

II. Give a macro definition of an extended %3SETQ%*, which is called 
as %3(SETQ#%1var%41%*#exp%41%*#...#var%4n%*#exp%4n%3)%1.
Each var%4i%* is a name; each exp%4i%* is an expression to be evaluated
and assigned to var%4i%1. The assignments should go from "left-to-right".

Thus %3(SETQ X 2 Y (TIMES 2 X) X 3)%* when executed should assign
%33%* to %3X%* and %34%* to %3Y%*.


We now wish  to extend our compiler to handle macro definitions.
Consider the example of defining %3plus%* of an indefinite number of arguments
given on {yon(P58)}.
In the presence of a compiler we can frequently make execution of macros
more efficient than their special form counterpart. This is the case with %3plus%*.
When %3plus%* is called we know the number of arguments, and can simply
expand the macro to a nest of calls on %3*plus%*. For example:
.begin centerit;

%3
←plus[4;add1[2];4] %1expands to%* *plus[4;*plus[add1[2];4]] %1
which can be efficiently compiled. 
.end

Macros can also be used effectively in implementing abstract data structures.
The constructors, selectors, and recognizers which help characterize
a data structure can be expressed as very simple S-expr operations.
These operations are performed quite frequently in a data structure algorithm
and so any increase in their running efficiency will be beneficial.
Recall on {yon(P60)} we defined %3coef%* 
as %3car%*. Compiled calls on %3coef%* would invoke the function-calling
mechanism, whereas many compilers can substitute actual hardware instructions
for calls on %3car%*, resulting in more efficient run-time code.
So for efficiency's sake it would be better to write %3car%* instead of
%3coef%*. There are two objections to this. First, %3coef%* has more
mnemonic significance than %3car%*. Second, using %3car%* we have explicitly
tied our algorithm to the representation. Both are strong
objections.
Macros can help overcome both objections. Define:

←%3coef <%4m%*= λ[[l]cons[CAR;cdr[l]]]%1.

The user writes %3(COEF ...)%*; the evaluator sees %3(COEF ...)%* and
finally evaluates %3(CAR ...)%*; and the compiler sees %3(COEF ...)%*
and compiles code for %3(CAR ...)%*. So we can get the efficient code, the
readibility, and flexibility of representation with macros.


Macros can also be used to perform most of the operations which special forms
are meant to do.
Since %3eval%* handles calls on special forms, we should examine the
extensions to %3compile%* to generate such code. We have seen that
in compiling  arguments to (normal) functions, we generate the code for
each, followed by code to save the result in the run-time stack, %3P%*.
The argument to a special form is %2unevaluated%*, by definition. All we
can thus do for a call of the form %3f[l]%*, where %3f%* is a special form,
is pass the argument, compiling something like:

.BEGIN CENTERIT;SELECT 3;GROUP;

←(MOVEI AC1 (%eR%f(%3 l %f)%3))
←(CALL 1 (E F))
.END

This should also be clear from the structure of %3FEXPR%* calling in the %aSM%*
evaluator. 


←%2Problems%*

I. Extend the last %3compile%* function to handle macros.

II. Assume ⊗→%3and%*↔← allows  an indefinite
number of arguments.  Show how to modify %3compile%* to recognize %3and%*
and compile efficient code for its execution.